Description
Solution
一个题目 个 你值得拥有
浅い夢だから 胸をはなれない
给定一张 n 个点 m 条边的无向图。当你在点 u 时,你可以花费 1 的费用向系统询问当前可以去哪个点,系统会从点 u 的所有出边中随机选择一条告诉你。你可以选择去,或者重新花费并询问。初始时刻你在 1 号点,要去 n 号点。求最少花费的期望。
1≤n,m≤3×105
Fibonacci 数列的性质很多,有的常考,有的不常考。
这些性质都有可能是解题关键。这里稍作总结。
Fibonacci 的定义很多,本文采取如下的递归定义:
给你 n 种颜色的球,每个球有 k 个,把这 n×k 个球排成一排,把每一种颜色的最左边出现的球涂成白色(初始球不包含白色),求最终有多少种不同的颜色序列,答案对 109+7 取模。
1≤n,k≤2×103
给定一张 n 个点 m 条边的图,一条边 (u,v) 有 31 的概率消失,31 的概率定向成 u→v ,31 的概率定向成 v→u 。求最后的图是 DAG 的概率。
n≤20,m≤2n(n−1)
一个不会整数划分的 sb 的自救
考虑一个这样的问题:给定 n,m ,求将 m 划分成不超过 n 个从 1 开始值域连续的整数的和的方案数。
有一个很明显的做法:设 fi,j,k 表示用了 i 个数,总和为 j ,目前最大数为 k 的方案数。转移比较明显: